package com.ai.zuochengyun.phase01.class06;

import java.util.*;

/**
 * 拓扑排序
 */
public class Code03_TopologySort {

    public static List<Node> sort(Graph graph) {
        // 某个节点剩余的入度
        Map<Node, Integer> inMap=  new HashMap<>();
        // 将剩余入度为0的节点加入队列中
        Queue<Node> zeroInQueue = new LinkedList<>();
        for (Node node : graph.nodes.values()) {
            if (node.in == 0) {
                zeroInQueue.add(node);
            }
        }

        List<Node> res = new ArrayList<>();
        while (!zeroInQueue.isEmpty()) {
            Node cur = zeroInQueue.poll();
            res.add(cur);
            // cur节点入度为0，已经排好序了，那么将其与next节点的关联移除，就表明将next节点的剩余入度减掉
            for (Node node : cur.nexts) {
                // 当前点的邻居点的入度，都减掉1，表示从当前点到邻居点的路移除
                inMap.put(node, inMap.get(node) - 1);
                // 剩余入度为0了，所以加入队列中
                if (inMap.get(node) == 0) {
                    zeroInQueue.add(node);
                }
            }
        }
        return res;
    }
}
